Typical DP Contest E - 数

解答

code: python

d = int(input())

n = input()

MOD = 1000000007

# dpijm := 上からi桁目を決める段階、今作成している数字の桁和をDで割った余りがj、今作成している数字が n 未満であることが確定しているかどうか(している場合は1)

dp = [[0 for _ in range(2) for _ in range(105)] for _ in range(10005)]

dp000 = 1

for i in range(1, len(n) + 1):

for j in range(d):

for k in range(10):

# i−1桁目まで決めた段階での桁和をDで割った余りがjのとき、i桁目をk(0 <= k <= 9)にすることを考える

now = int(ni - 1)

if now > k:

# i−1桁目を決める時点でN未満であることが確定しているかどうかにかかわらず、

# i+1桁目以降でどんな数字を当てはめてもN未満になる

elif now == k:

# N未満が確定しているかどうかは、i−1桁目の時点でN未満であることが確定しているかどうかに依存

else:

# N未満であることがi−1桁目の時点で決まっていれば良いが、

# そうでない場合は、i桁目でkを選ぶとNを超えてしまうので、問題の条件を満たさなくなる

# 正整数が条件なので、0を省く

print((dplen(n)00 + dplen(n)01 - 1) % MOD)

テーマ

メモ

提出

code: python

d = int(input())

n = int(input())

# dpi := i の各桁の数の和

# i <= pow(10, 100000) TLE

# dpi := i の倍数であるものの個数

dp = 0 * (100 + 1)